home *** CD-ROM | disk | FTP | other *** search
/ The Programmer Disk / The Programmer Disk (Microforum).iso / xpro / c4 / pro13 / maketre_.asm < prev    next >
Assembly Source File  |  1991-02-11  |  6KB  |  311 lines
  1. ;***********************************************
  2. ;    maketree.asm -- makes Huffman tree
  3. ;***********************************************
  4.             page    0, 128
  5.  
  6. include    amscls.inc
  7. $_init    GEN
  8.  
  9. TEXT    segment    byte    public    'CODE'
  10. TEXT    ends
  11.  
  12. DATA    segment word    public    'DATA'
  13. DATA    ends
  14.  
  15. BSS        segment word    public    'DATA'
  16. extrn    right_:word
  17. extrn    left_:word
  18.  
  19. extrn    nchar:word
  20. extrn    n2:word
  21. extrn    avail_mt:word
  22. extrn    heapsize:word
  23. extrn    freq:word
  24. extrn    sort:word
  25. extrn    bitlen:word
  26. extrn    code:word
  27. extrn    depth:word
  28. extrn    heap:word
  29. extrn    len_cnt:word
  30. extrn    start:word
  31. extrn    weight:word
  32. BSS        ends
  33.  
  34. DGROUP    group    DATA, BSS
  35.  
  36. TEXT    segment    byte    public    'CODE'
  37.     assume    cs:TEXT, ds:DGROUP
  38. ;---------------------------------------------------------------
  39. ;    static void count_len(short i)  /* call with i = root */
  40. ;
  41. ;---------------------------------------------------------------
  42. public    count_len
  43. count_len    proc    near
  44.     $_if <cmp bx, n2>, B
  45.         mov        bx, depth
  46.         $_if <cmp bx, 16 * 2>, A
  47.             mov        bx, 16 * 2
  48.         $_endif
  49.         inc        len_cnt[bx]
  50.         ret
  51.     $_endif
  52.     add        depth, 2
  53.     push    bx
  54.     mov        bx, left_[bx]
  55.     call    count_len
  56.     pop        bx
  57.     push    bx
  58.     mov        bx, right_[bx]
  59.     call    count_len
  60.     pop        bx
  61.     shr        left_[bx], 1
  62.     shr        right_[bx], 1
  63.     sub        depth, 2
  64.     ret
  65. count_len    endp
  66.  
  67. ;---------------------------------------------------------------
  68. ;    static void downheap(short i)
  69. ;                              bx
  70. ;---------------------------------------------------------------
  71. public    downheap
  72. downheap    proc    near
  73.     push    cx
  74.     push    dx
  75.     push    si
  76.     push    di
  77.     push    bp
  78.     mov        si, heap[bx]
  79.     push    si
  80.     mov        bp, freq
  81.     mov        cx, ds:[bp + si]
  82.     mov        si, bx
  83.     $_while <TRUE>
  84.         shl        si, 1
  85.         $_break , <cmp si, heapsize>, A
  86.         mov        di, heap[si]
  87.         mov        ax, ds:[bp + di]
  88.         $_if , B, AND
  89.             mov        di, heap[si + 2]
  90.             mov        dx, ds:[bp + di]
  91.         $_c  <cmp ax, dx>, A
  92.             mov        ax, dx
  93.             add        si, 2
  94.         $_endif
  95.         $_break , <cmp cx, ax>, BE
  96.         mov        di, heap[si]
  97.         mov        heap[bx], di
  98.         mov        bx, si
  99.     $_enddo
  100.     pop        heap[bx]
  101.     pop        bp
  102.     pop        di
  103.     pop        si
  104.     pop        dx
  105.     pop        cx
  106.     ret
  107. downheap    endp
  108.  
  109. ;---------------------------------------------------------------
  110. ;    short make_tree(short nparm, ushort freqparm[], 
  111. ;                             cx               bx
  112. ;                    uchar lenparm[], ushort codeparm[])
  113. ;                               di                 ax
  114. ;---------------------------------------------------------------
  115. public    make_tree_
  116. make_tree_    proc    near
  117.     push    cx
  118.     push    dx
  119.     push    si
  120.     push    di
  121.     push    bp
  122.     mov        nchar, ax
  123.     mov        freq, bx
  124.     mov        bitlen, cx
  125.     mov        code, dx
  126.     shl        ax, 1
  127.     mov        n2, ax
  128.     mov        avail_mt, ax
  129.  
  130.     xor        ax, ax
  131.     cld
  132.     push    ds
  133.     pop        es
  134.     mov        di, cx
  135.     mov        cx, nchar
  136.     rep        stosb
  137.  
  138.     mov        cx, nchar
  139.     mov        di, freq
  140.     lea        dx, 2[di]
  141.     mov        bx, offset DGROUP:heap
  142.     jmp        make_tree_1
  143.     $_do
  144.         add        bx, 2
  145.         mov        [bx], di
  146.         sub        [bx], dx
  147. make_tree_1:
  148.         xor        ax, ax                    ; set ZERO flag
  149.     $_until <repz scasw>, Z
  150.  
  151.     sub        bx, offset DGROUP:heap
  152.     mov        heapsize, bx
  153.     $_if <cmp bx, 4>, B
  154.         mov        ax, heap[2]
  155.         mov        di, ax
  156.         add        di, code
  157.         mov        word ptr [di], 0
  158.         jmp        return
  159.     $_endif
  160.     shr        bx, 1
  161.     and        bx, 0fffeh
  162.     $_do
  163.         push    bx
  164.         call    downheap
  165.         pop        bx
  166.     $_until <sub bx, 2>, Z
  167.     mov        di, code
  168.     $_do
  169.         mov        si, heap[2]
  170.         $_if <cmp si, n2>, B
  171.             mov        [di], si
  172.             add        di, 2
  173.         $_endif
  174.  
  175.         mov        bx, heapsize
  176.         sub        heapsize, 2
  177.         mov        ax, heap[bx]
  178.         mov        heap[2], ax
  179.  
  180.         mov        bx, 2
  181.         call    downheap
  182.  
  183.         mov        dx, heap[2]
  184.         $_if <cmp dx, n2>, B
  185.             mov        [di], dx
  186.             add        di, 2
  187.         $_endif
  188.  
  189.         mov        bx, avail_mt
  190.         add        avail_mt, 2
  191.  
  192.         mov        left_[bx], si
  193.         mov        right_[bx], dx
  194.         mov        heap[2], bx
  195.  
  196.         mov        bp, freq
  197.         mov        ax, [si + bp]
  198.         mov        si, dx
  199.         add        ax, [si + bp]
  200.         mov        dx, bx
  201.         add        bx, bp
  202.         mov        [bx], ax
  203.  
  204.         mov        bx, 2
  205.         call    downheap
  206.     $_until <cmp heapsize, 2>, BE
  207.     mov        bx, dx
  208.     push    dx
  209. ;---------------------------------------------------------------
  210. ;    static void make_len(short root)
  211. ;---------------------------------------------------------------
  212. public    make_len
  213. make_len:
  214.     xor        ax, ax
  215.     mov        di, offset DGROUP:len_cnt
  216.     mov        cx, 17
  217.     rep        stosw
  218.     mov        depth, ax
  219.     call    count_len
  220.     xor        dx, dx
  221.     mov        cx, 15
  222.     mov        si, offset DGROUP:len_cnt + 2
  223.     $_do
  224.         lodsw
  225.         shl        ax, cl
  226.         add        dx, ax
  227.     $_until <LOOP>
  228.     add        dx, [si]
  229.     $_if , NZ
  230.         sub        len_cnt[16 * 2], dx
  231.         mov        cx, dx
  232.         $_do
  233.             mov        di, offset DGROUP:len_cnt + 15 * 2
  234.             $_while <cmp word ptr [di], 0>, E
  235.                 sub        di, 2
  236.             $_enddo
  237.             dec        word ptr [di]
  238.             add        word ptr [di + 2], 2
  239.         $_until <LOOP>
  240.     $_endif
  241.     mov        di, offset DGROUP:len_cnt + 16 * 2
  242.     mov        si, code
  243.     mov        al, 16
  244.     $_do
  245.         mov        cx, [di]
  246.         jcxz    make_len_1
  247.         $_do
  248.             mov        bx, [si]
  249.             add        si, 2
  250.             shr        bx, 1
  251.             add        bx, bitlen
  252.             mov        [bx], al
  253.         $_until <LOOP>
  254. make_len_1:
  255.         sub        di, 2
  256.         dec        al
  257.     $_until , Z
  258. ;---------------------------------------------------------------
  259. ;    void make_code(short nchar, uchar bitlen[], ushort code[])
  260. ;---------------------------------------------------------------
  261. public    make_code
  262. make_code:
  263.     xor        ax, ax
  264. ;;;
  265.     mov        start, ax
  266.     mov        weight, ax
  267. ;;;
  268.     mov        si, offset DGROUP:len_cnt + 2
  269.     mov        di, offset DGROUP:start + 2
  270.     mov        bx, offset DGROUP:weight + 2
  271.     mov        cx, 16
  272.     $_do
  273.         stosw
  274.         mov        dx, [si]
  275.         add        si, 2
  276.         dec        cx
  277.         shl        dx, cl
  278.         add        ax, dx
  279.         mov        dx, 1
  280.         shl        dx, cl
  281.         inc        cx
  282.         mov        [bx], dx
  283.         add        bx, 2
  284.     $_until <LOOP>
  285.     xor        bx, bx
  286.     mov        cx, nchar
  287.     mov        si, bitlen
  288.     mov        di, code
  289.     $_do
  290.         lodsb
  291.         shl        al, 1
  292.         mov        bl, al
  293.         mov        ax, start[bx]
  294.         stosw
  295.         mov        ax, weight[bx]
  296.         add        start[bx], ax
  297.     $_until <LOOP>
  298. ;---------------------------------------------------------------
  299.     pop        ax
  300. return:
  301.     shr        ax, 1
  302.     pop        bp
  303.     pop        di
  304.     pop        si
  305.     pop        dx
  306.     pop        cx
  307.     ret
  308. make_tree_    endp
  309. TEXT    ends
  310.         end
  311.